With the advance of digital technologies, especially as found in the Internet and in the digital camera, the use of pictures as a universal language is getting easier and more efficient. However, the number of digital images, including personal collections, is increasing exponentially. Therefore, there is a growing need for an effective and efficient organization of a collection of unsorted digital pictures into coherent and similar groups. Such organized pictures are easier to use, more efficient to browse and retrieve, and more effective to present and display, making picture taking more fun and enjoyable.
The wide variety of image organization schemes can be classified as supervised or unsupervised, content-based or non-content-based, fully automatic or semi-automatic.
Supervised image classification requires extensive training before classification can succeed. People have to provide a training set comprised of examples (images and their membership labels) so that the system can build up a decision tree. Given a test image outside of the training set, the system tries to assign an appropriate membership label to it. One of such schemes is reported in “An automatic hierarchical image classification scheme”, Proceedings of ACM Multimedia 1998, in the names of J. Huang, S. R. Kumar and R. Zabih. The article teaches a supervised, content-based and fully automatic approach to image classification. However, supervised training requires a priori knowledge about the data set, which is not always available. And the performance depends on how well the training data sets match the upcoming unsorted images. The paper does not suggest how to classify images when such training data is not available.
Some schemes use auxiliary metadata attached to each digital image, such as the date and time of capture or temporal order of the pictures, for image grouping. Previous articles taking this approach include: “AutoAlbum: Clustering digital photographs using probabilistic model merging”, Proceedings of IEEE Workshop on Content-based Access of Image and Video Libraries, 2000, in the name of John C. Platt; “Automatic image event segmmentation and quality screening for albuming applications”, Proceedings of IEEE ICME 2000, in the names of A. Loui and A. Savakis; “Discovering recurrent visual semantics in consumer photographs”, Proceedings of ICIP 2000, in the names of A. Jaimes, A. B. Benitez, S.-F. Chang and A. Loui; and commonly-assigned U.S. patent application Ser. No. 09/163,618, “A method for automatically classifying images into events”, filed Sep. 30, 1998 in the names of A. Loui and E. Pavie. The problem is that these methods depend on the auxiliary metadata, which is not always available for all images.
Other schemes use a content-based approach to test image similarity. The content-based approach refers to methods that analyze the image content, such as spatial color distribution, texture, shape, location, geometry, etc. U.S. Pat. No. 6,246,790, “Image indexing using color correlograms”, teaches a low-level feature color correlogram and how to use it for image indexing. A color correlogram is a three-dimensional graph or table indexed by color and distance between pixels showing how the spatial correlation of color changes with distance in an image. Each entry (i, j, k) in the table is the probability of finding a pixel of color ci at a selected distance k from a pixel of color cj. In U.S. Pat. No. 6,246,790, which is incorporated herein by reference, the color correlogram has been shown to have better performance than a color histogram as a low-level feature. U.S. Pat. No. 5,963,670, “Method and apparatus for classifying and identifying images”, teaches a system and methods to use relative relationships between image patches encoded in a global deformable template for image classification and identification. U.S. Pat. No. 5,911,139, “Visual image database search engine which allows for different schema”, teaches a search engine for content-based search and retrieval of visual objects. U.S. Pat. No. 5,852,823, “Image classification and retrieval system using a query-by-example paradigm”, teaches image retrieval by examples. The task addressed in the foregoing four patents is one of image retrieval, that is, finding similar images from an image database. The task is different than image grouping, i.e., organizing images into coherent and similar groups. Furthermore, U.S. Pat. No. 6,246,790 does not suggest the application of a color correlogram for semi-automatic image grouping, and does not address efficient manipulation of color correlograms.
While a fully manual approach is not of much interest due to the amount of time and effort needed to sort through the pictures, a fully automatic content-based approach is very challenging, if not impossible, to achieve mainly because of the involved subjectivity. Given the same set of pictures, people with different background knowledge, emphasis, focus, emotion and criteria may not come up with the exact same grouping results. However, there is strong evidence that people tend to put visually similar pictures and images of the same subjects taken at the same time and location in the same group.
There is a need therefore for an improved method and system for unsupervised, content-based and semi-automatic image grouping.